//给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1], k = 2
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3], k = 3
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 104 
// -1000 <= nums[i] <= 1000 
// -107 <= k <= 107 
// 
// Related Topics 数组 哈希表 前缀和 
// 👍 1138 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func subarraySum(nums []int, k int) int {
	// 前缀和

	ans := 0

	if len(nums) == 0 {
		return 0
	}

	// 构造前缀和
	preSum := make([]int, len(nums) + 1)  // 冗余一位留给 -1状态
	preSum[0] = 0
	for i := 0; i < len(nums); i++ {
		preSum[i + 1] = preSum[i] + nums[i]
	}

	// 使用前缀和
	for i := len(nums); i >= 0; i-- {
		for j := i - 1; j >=0; j-- {
			if preSum[i] - preSum[j] == k {
				ans++
			}
		}
	}

	return ans

	// 前缀和变种优化 记录前缀和出现次数 直接计算sum -k 出现多少次
}
//leetcode submit region end(Prohibit modification and deletion)
